/**
 * Universidad del Valle de Guatemala
 * Algoritmos y Estructura de Datos
 * Rodrigo Avelar; carné: 11192
 * programa basado de ejemplos en Java Structures de Duane A. Bailey
 */
import java.util.*;

public class Main {
     public static void main(String[] args) {  
         
        System.out.print("Ingrese un mensaje: "); 
        // Ingreso de texto:
        Scanner in = new Scanner(System.in);
        
        // Se genera un arreglo con cada uno de los caracteres del mensaje
        String cadena = in.next();
        char[] arreglo = new char[cadena.length()];
        cadena.getChars(0, cadena.length(), arreglo, 0);
        
        // Se genera una lista que almacenan el caracter y la frecuencia
        List<Nodo> listaFreq = new LinkedList<>();
        
        for(int i = 0; i < cadena.length(); i++){
            char caracter = arreglo[i];
            int frecuencia = 1;
            for(int j = i + 1; j < cadena.length(); j++){
                if(arreglo[j]==caracter){
                    frecuencia++;
                }
            }
            Nodo nodo = new Nodo(caracter, frecuencia);
            listaFreq.add(nodo); 
            // Se compara si la letra ya se almaceno en un nodo previo
            char letra1;
            char letra2 = (char)nodo.getCaracter();
            for(int j = 0; j < listaFreq.size() - 1; j++){
                letra1 = (char)(listaFreq.get(j)).getCaracter();
                if(letra2 == letra1){
                    listaFreq.remove(listaFreq.size() - 1);
                }
            }
        }     
        
        Nodo[] arrayCaracterFrecuencia = new Nodo[listaFreq.size()];
        for(int i = 0; i < listaFreq.size(); i++){
            arrayCaracterFrecuencia[i] = listaFreq.get(i);
        }
        
        // Se crea el Árbol de Huffman y el Heap que almacena los arboles
        ArbolHuffman arbolDeHuffman = new ArbolHuffman(arrayCaracterFrecuencia);
        
        // Se generan los códigos de los nodos.
        arbolDeHuffman.setCodes();
        
        // despliegue de tabla de codigos
        System.out.println("Caracter  " + "  Frecuencia  " + "     Código");
        for(int i = 0; i < arrayCaracterFrecuencia.length; i++){
            Nodo nodo = arrayCaracterFrecuencia[i];
            System.out.println("    " + nodo.getCaracter() + "\t\t" + nodo.getFrecuencia() 
                    + "\t\t" + nodo.getCodigo());
        }
    }
    
}
